package demo2;
import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
public class Solution {
    //1.二叉搜索树中的搜索(广度优先遍历)
/*    public TreeNode searchBST(TreeNode root, int val) {
        //BFS
        while(root != null) {
            if(val < root.val) {
                root = root.left;
            }else if(val > root.val) {
                root = root.right;
            }else {
                return root;
            }
        }
        return null;
    }
    //2.相同的树
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) {
            return true;
        }
        if(p == null && q != null || p != null && q == null) {
            return false;
        }
        if(p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    //3.另一棵树的子树
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q != null || p != null && q == null){
            return false;
        }
        if(p == null && q == null){
            return true;
        }
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //空树不不会有子集
        if(root == null) {
            return false;
        }
        //先判断跟结点是不是两颗相同的树
        if(isSameTree(root, subRoot)) {
            return true;
        }
        //再去递归下去，看左右子树是否为子树
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    //4.剑指 Offer 26. 树的子结构
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null) {
            return false;
        }
        //先判断跟结点是不是两颗相同的树
        if(isSameTree(A, B)) {
            return true;
        }
        //再去递归下去，看左右子树是否为子树
        return isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    //判断是不是两颗相同的树
    private boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) {
            return true;
        }
        if(p != null && q == null) {
            return true;
        }
        if(p == null && q != null) {
            return false;
        }
        if(p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }*/
    //5.剑指 Offer 55 - II. 平衡二叉树
    public boolean isBalanced(TreeNode root) {
        //空树也是平衡的
        if(root == null) {
            return true;
        }
        //先判断根节点是否为平衡二叉树
        if(Math.abs(maxDepth(root.left) - maxDepth(root.right)) > 1) {
            return false;
        }
        //再去看左右子树是否为平衡二叉树
        return  isBalanced(root.left) && isBalanced(root.right);
    }
    private int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
    //6.剑指 Offer 55 - II. 平衡二叉树(优化时间复杂度为O(n))
/*    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
        //dfs一旦判断出不平衡就会返回-1
        return dfs(root) >= 0;
    }*/
    //求树的高度(深度优先搜索)
    private int dfs(TreeNode root) {
        if(root == null) {
            return 0;
        }
        //递归求出左树右树高度
        int leftHigh = dfs(root.left);
        int rightHigh = dfs(root.right);
        //比较差值
        if(leftHigh >= 0 && rightHigh >= 0 && Math.abs(leftHigh - rightHigh) <= 1) {
            return Math.max(leftHigh, rightHigh) + 1;
        }else {
            //不满足就返回-1，因为高度不可能是-1；
            return -1;
        }
    }
    //7.对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }
        //一个参数无法解决，就换成两参数
        return isSymmetricChild(root.left, root.right);
    }
    private boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
        //都为空对称
        if(leftTree == null && rightTree == null) {
            return true;
        }
        //一个为空一个不为空，不对称
        if((leftTree == null && rightTree != null) || (leftTree != null && rightTree == null)) {
            return false;
        }
        if(leftTree.val != rightTree.val) {
            return false;
        }
        //递归
        return isSymmetricChild(leftTree.left, rightTree.right) &&
                isSymmetricChild(leftTree.right, rightTree.left);
    }
    //8.剑指 Offer 07. 重建二叉树
    public int cur;//找根节点的下标
    private TreeNode buildTreeChild(int[] preorder, int[] inorder, int start, int end) {
        if(start > end) {
            return null;
        }
        //在中序遍历中找到cur对应的下标元素
        int index = fundIndex(preorder, inorder);
        TreeNode root = new TreeNode(inorder[index]);//创建根节点
        //递归创建左右子树
        root.left = buildTreeChild(preorder, inorder, start, index - 1);
        root.right = buildTreeChild(preorder, inorder, index + 1, end);
        return root;
    }
    private int fundIndex(int[] preorder, int[] inorder) {
        for(int i = 0; i < inorder.length; i++) {
            if(preorder[cur] == inorder[i]) {
                cur++;
                return i;
            }
        }
        return -1;//没找到
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder, inorder, 0, preorder.length - 1);
    }

    //9.剑指 Offer 33. 二叉搜索树的后序遍历序列
    public boolean verifyPostorder(int[] postorder) {
        return divided(postorder, 0, postorder.length - 1);
    }
    private boolean divided(int[] postorder, int start, int end) {
        if(start >= end) {//只有一个结点也算是后序遍历的结果
            return true;
        }
        //从左往右找出第一个大于根节点的结点
        int s = start;
        while(postorder[s] < postorder[end]) {
            s++;
        }
        //从一个大于根节点的结点开始直到end - 1，都因该大于根节点
        int b = s;
        while(postorder[s] > postorder[end]) {
            s++;
        }
        //继续递归分割                            //这里取下一个界(搜索树性质)
        return s == end && divided(postorder, start, b - 1) &&
                divided(postorder, b, end - 1);//这里取下一个根节点
    }
    //10.路径总和(dfs)
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) {
            return false;
        }
        //把每个结点看成叶子结点(先从根入手)
        if(root.left == null && root.right == null) {
            return root.val == targetSum;
        }
        //递归去看左树右树
        return hasPathSum(root.left, targetSum - root.val) ||
                hasPathSum(root.right, targetSum - root.val);
    }
    //二叉树的直径
    private int max;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null) {
            return 0;
        }
        maxDepth(root);
        return max;
    }
    //求最大深度
/*    private int maxDepth(TreeNode root) {
        if(root.left == null && root.right == null) {
            return 0;
        }
        int left = root.left == null ? 0 : maxDepth(root.left) + 1;
        int right = root.right == null ? 0 : maxDepth(root.right) + 1;
        max = Math.max(left + right, max);
        return Math.max(left, right);
    }*/

}
